class Solution {
    public int minDistance(int[] houses, int k) {
        Arrays.sort(houses);
        int n = houses.length;
 
        // rec[i][j] 表示第 i 个房子(houses[i - 1]) 到第 j 个房子(houses[j - 1]) 中间放一个邮筒，距离和的最小值
        int[][] rec = new int[n + 1][n + 1];
 
        for (int i = 1; i <= n; i++) {
            for (int j = i; j <= n; j++) {
                int mid = i + j >> 1;
                for (int x = i; x <= j; x++) {
                    rec[i][j] += Math.abs(houses[mid - 1] - houses[x - 1]);
                } 
            }
        }
 
        // dp[i][j] 表示前 i 个房子(houses[0] ~ houses[i - 1]), 用了 j 个邮筒，距离和的最小值
        int[][] dp = new int[n + 1][k + 1];
 
        // 初始化 dp[1][1] ~ dp[n][1], dp[1][2] ~ dp[1][k]  
        for (int i = 1; i <= n; i++) {
            dp[i][1] = rec[1][i]; // 从第一个房子到第 i 个房子
        }
        for (int j = 2; j <= k; j++) {
            dp[1][j] = Integer.MAX_VALUE;
        }
 
        // dp[i][j] = min{dp[x][j - 1] + rec[x + 1][i] | j - 1 <= x <= i - 1}
        // x = j - 1 表示前 j - 1 个房子各对应一个邮筒， 第 j 个房子到第 i 个房子对应第 j 个邮筒
        // x = i - 1 表示前 i - 1 个房子对应前 j - 1 个邮筒，第 i 个房子对应第 j 个邮筒
        for (int i = 2; i <= n; i++) {
            for (int j = 2; j <= k && j <= i; j++) {
                dp[i][j] = Integer.MAX_VALUE;
                for (int x = j - 1; x <= i - 1; x++) {
                    dp[i][j] = Math.min(dp[x][j - 1] + rec[x + 1][i], dp[i][j]);
                }
            }
        }
        return dp[n][k];
    }
}